//给定一个非负整数数组，你最初位于数组的第一个位置。 
//
// 数组中的每个元素代表你在该位置可以跳跃的最大长度。 
//
// 判断你是否能够到达最后一个位置。 
//
// 示例 1: 
//
// 输入: [2,3,1,1,4]
//输出: true
//解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
// 
//
// 示例 2: 
//
// 输入: [3,2,1,0,4]
//输出: false
//解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
// 
// Related Topics 贪心算法 数组 
// 👍 952 👎 0


package com.yun.leetcode.editor.cn;

public class JumpGame {
    public static void main(String[] args) {
        Solution solution = new JumpGame().new Solution();
//        System.out.println(solution.canJump(new int[]{0}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 这种解法，类似在更新，你手最远能伸到多长，
        // 能伸很长就维护最大值，能摸到最后一位就能到
        public boolean canJump(int[] nums) {
            //用max记录能到达的最远位置
            int max = 0;
            //从头开始遍历
            for(int i = 0; i < nums.length; i++){
                //如果当前位置小于等于可达的最远位置
                if(i <= max){
                    //更新最远可达位置
                    max = Math.max(max, i + nums[i]);
                    //满足条件直接退出，不需要再遍历后续位置
                    if(max >= nums.length - 1){
                        return true;
                    }
                }
            }
            return false;
        }

        // 这种解法类似，一个人在上面走，然后补充能量。
        public boolean canJump1(int[] nums) {
            int start = 1;
            int length = nums.length;

            for (int i = 0; i < length; i++) {
                start--;
                start = Math.max(start, nums[i]);
                if (start == 0 && i < length-1) {
                    return false;
                }

            }
            return true;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}